When a subscriber line is accommodated using a TDM (time division multiplexing) technology, there is a technique to determine which TDM transmission line is used to accommodate the line. It is necessary to use the technique on the network for transmission using the TDM transmission line by a WDM (wavelength division multiplexing) technique.
Since the signal of the subscriber line accommodated in the TDM transmission line is called a traffic demand or simply a demand, the subscriber line accommodated in the TDM transmission line is called a demand in the following explanation.
When a signal (demand) of a subscriber line is transmitted using a fiber laid between the telephone stations, the demands for which a transmission may be performed using the same fiber are transmitted by multiplexing in the TDM transmission line the demands capable of being transmitted using the same fiber. In this case, it is necessary to determine which demand is to be multiplexed in which TDM transmission line. Thus, when a demand to be accommodated and a network topology are given, it is necessary to solve the problem to determine section and capacity of the TDM transmission line. The problem is hereafter referred to as an accommodation designing problem.
The recent communications are completely digitized, and a plurality of places are prepared for a signal called a time slot in the TDM transmission line. When a demand is assigned to the TDM transmission line, the number of time slots is determined depending on the bandwidth of the demand to be assigned. Therefore, when the demand to be accommodated in a given TDM transmission line is determined, it is necessary to prevent the total number of time slots required by the demand to be accommodated from exceeding the number of time slots prepared for the TDM transmission line. Furthermore, one TDM transmission line occupies one wavelength of the WDM, and the number of wavelengths which may be accommodated in one fiber depends on the system. Therefore, it is necessary to perform designing so that the number of TDM transmission lines does not exceed the number of wavelengths accommodated for each fiber.
Conventionally, an SDH (synchronous digital hierarchy) transmission line has been mainly used as a TDM transmission line. For the SDH, the smallest unit of the time slot such as an STM 1 is given, and the number of time slots of a demand is 1, 4, 16, etc. which indicates an integral multiple to one another, and is set as a value. In some cases, a demand uses an undivided number of time slots. In most of the cases, the demand is temporarily stored in a line in which the demand may be accommodated and the number of time slots is an integral multiple of time slots, and the accommodation line is multiplexed as a demand in the TDM transmission line.
Recently, an OTN (optical transport network) technique has been standardized. In the OTN, the accommodated demand may have the speed of any integral multiple of the minimum speed. That is, the demand having the number of time slots which does not indicate an integral multiple of the total number of time slots of the TDM transmission line and the number of time slots of another demand may be freely multiplexed.
There is a method for solving the accommodation designing problem by a mathematical programming under the conditions. When the mathematical programming is used, each TDM transmission line is prepared in advance to solve the problem as 0-1 programming by determining to use or not to use each line. Another method is to prepare in advance a section of the TDM transmission line defined by the start and end points and the path between them, and determine the number of necessary TDM transmission lines in the section for each speed. Then, the demand to be accommodated in each TDM transmission line is determined from the obtained number of TDM transmission lines and the list of demands to be accommodated. That is, the problem is solved by two stages. In the first method, a variable is assigned to each of the prepared TDM transmission lines. In the second method, a variable is assigned to each section of the TDM transmission line. Therefore, in the first method, the size of a network and the number of demands for practically solving the problem are considerably limited by the capacity of the equipment for performing computation. Accordingly, in a large recent network, the calculating time to solve the problem becomes unpractically very long. On the other hand, in the second method, the problem of determining the demand to be accommodated in each TDM transmission line is solved by solving a part of the original problem as another problem after determining the number of TDM transmission lines. In this case, there is a solution for accommodating all demands without fail in the TDM transmission lines of the number calculated from the number of time slots if the number of time slots required by the demand and the number of time slots prepared for the TDM transmission line indicate the relationship of integral multiples as in the case of the SDH. However, there occurs a case in which demands are not accommodated using the TDM transmission lines of the number calculated from the number of time slots by the demands which occur regardless of the relationship of integral multiples since the OTN technology has been used.
In the following explanation, the number of necessary time slots in accommodating a signal is expressed as the bandwidth of the demand, and the total number of time slots of the TDM transmission line is expressed as the capacity of the TDM transmission line. For example, assume that there are five demands to be accommodated, the number of respective bands is 6, and the capacity of the TDM transmission line is 8. Since there are five demands each having six bands, the total number of necessary time slots, that is, the total number of bands is 30. Therefore, if there are four TDM transmission lines each having the capacity of 8, the total number of time slots, that is, the total capacity, is 32 which permits the accommodation. However, since one demand is not divided for accommodation in two TDM transmission lines, only one demand having six bands may be accommodated in one TDM transmission line, thereby requiring five TDM transmission lines. Thus, since the bandwidth of a demand is not limited to the relationship of integral multiples, there may occur the case in which the number of TDM transmission lines increases when the demand to be accommodated in each TDM transmission line is determined in the course of solving the problem and determining the number of necessary TDM transmission lines.
In the above-mentioned method in which the problem is solved in two stages, the number of TDM trans mission lines does not exceed the number of wavelengths available in the WDM when the necessary number of TDM transmission lines is determined for each section in which the TDM transmission line at the first stage. Therefore, if the number of TDM transmission lines increases when the demand to be accommodated in each TDM transmission line at the second stage is determined, then the number of wavelengths available in the WDM is exceeded, thereby incurring a result of invalid design. For example, in the above-mentioned example, if the number of TDM transmission lines accommodated in the WDM is four, the number of necessary TDM transmission lines is four, which is the solution for the accommodation in the WDM. However, the number of TDM transmission lines is five when the signal to be accommodated in each TDM transmission line at the second stage is determined, which is the accommodation not allowed in the WDM network.
To avoid the problem, a TDM transmission line of a larger capacity is used. Conventionally, if the number of TDM transmission lines increases when the demand to be accommodated in each TDM transmission line at the second stage is determined, then a transmission line of a larger capacity is used. In the above-mentioned example, three TDM transmission lines of the capacity of 8 are prepared, and one more TDM transmission line of double capacity of 16 is prepared, two demands of the band of 6 are accommodated in the TDM transmission line of the capacity of 16, thereby accommodating a total of four TDM transmission lines. In this method, a solution is expected in most cases when a TDM transmission line of a large capacity is prepared. Therefore, it is a very simple method in which the process is performed only at the second stage when the problem is solved in two stages. The method is effective when it is rare that the number of TDM transmission lines exceeds the number of available wavelengths. However, when the number of TDM transmission lines frequently exceeds the number of wavelengths available in the WDM, an excess number of TDM transmission lines of a larger capacity may be used. Generally, a TDM transmission line of a large capacity is expensive, and consequently a costly network is designed.
FIGS. 1 through 6 are explanatory views of the prior art.
As illustrated in FIG. 1, the network is configured by five nodes, that is, nodes A, B, C, D, and E, and it is assumed that a WDM transmission line available up to eight waves of wavelength for a fiber is used for each of A-B, B-C, C-D, and D-E. In this case, the number of TDM transmission lines passing between A and B, B and C, C and D and D and E is eight, that is, a total of 64 in capacity. In the following explanation, the portion of the connection between the nodes is called a link. Each of the A-B, B-C, C-D, and D-E in FIG. 1 is a link.
Next, FIG. 2 illustrates a demand to be accommodated. The start and end points, the bandwidth, and the number of lines are listed. It is assumed that the TDM transmission line is provided between A and B, B and C, C and D, D and E, and A and E as illustrated in FIG. 3. In FIG. 3, the section indicated by the arrow is the section where the TDM transmission line is set. For simplicity, it is assumed that the demand between A and B is accommodated in the TDM transmission line between A and B, the demand between B and C is accommodated in the TDM transmission line between B and C, the demand between C and D is accommodated in the TDM transmission line between C and D, the demand between D and E is accommodated in the TDM transmission line between D and E, and the demand between A and E is accommodated in the TDM transmission line between A and E. The total bandwidth between A-B and D-E is 6 bands×5, that is, 30, as illustrated in FIG. 2, and the number of necessary TDM transmission lines in computation is four. In addition, the total bandwidth between B-C is 4 bands×4, that is, 16, and the number of necessary TDM transmission lines in computation is two. The total bandwidth between C-D is 2 bands×8 that is, 16, and the number of necessary TDM transmission lines in computation is two. The total bandwidth between A-E is 4 bands×8, that is, 32, and the number of necessary TDM transmission lines in computation is four. FIG. 4 illustrates the total number of TDM transmission lines obtained from the total bandwidth of the demand between A-B, B-C, C-D, and D-E. For example, in the case between A and B, four TDM transmission lines are used between A and B, and four TDM transmission lines are used between A and E, that is, a total of eight lines are used. In this case, no link exceeds the number of wavelengths available in the WDM.
Next, the demand to be accommodated in each TDM transmission line is determined. First, since two demands each having a bandwidth of 4 may be accommodated in two TDM transmission lines having the capacity of 8 between B and C, two TDM transmission lines may be used for accommodation as computed when each TDM transmission line is used for accommodation. Furthermore, since two demands each having a bandwidth of 4 may be accommodated in two TDM transmission lines having the capacity of 8 between C and D, two TDM transmission lines may be used for accommodation as computed. Similarly, two demands each having a bandwidth of 4 may be accommodated in four TDM transmission lines having the capacity of 8 between A and E. However, between A and B and between D and E, the number of TDM transmission lines calculated from the total bandwidth is four, but five lines are required when each TDM transmission line is practically used for accommodation. That is, between A and B and between D and E, six bands are used for the demand. Therefore, the TDM transmission line having the capacity of 8 may accommodate only one demand. Accordingly, five TDM transmission lines are required for five demands. Therefore, although FIG. 5 illustrates the number of practically necessary TDM transmission lines, the number of wavelengths available for the WDM is exceeded between A and B and between D and E.
Thus, in the prior art technology, the number of necessary TDM transmission lines is reduced to the original number using the TDM transmission line having a larger capacity for the section in which the number of TDM transmission lines is exceeded in the TDM transmission lines which pass through the link where the number of TDM transmission lines has exceeded the number of wavelengths available for the WDM.
FIG. 6 is a flowchart of the prior art.
The network information such as the topology, the demand to be accommodated, the section in which a TDM transmission line is set, etc. is input (step S10). Next, the accommodation designing problem is solved to determine the number of TDM transmission lines in each section (step S11). Then, the demand to be accommodated in each TDM transmission line is determined (step S12). Then, each link is checked whether or not the number of TDM transmission lines has exceeded the number of wavelengths available in the WDM (step S13). If there is no link in which the number of TDM transmission lines has exceeded the number of wavelengths available in the WDM, the process is terminated. If there is a link in which the number of TDM transmission lines has exceeded the number of wavelengths available in the WDM, the section of the TDM transmission line which passes through the link in which the number of TDM transmission lines exceeds the number of available wavelengths is listed (step S14). Then, the sections are sequentially retrieved (step S15), and it is checked whether or not the number of TDM transmission lines has increased when the demand to be accommodated in each TDM transmission line is determined from the number of the TDM transmission lines when the number of TDM transmission lines for each section is determined (step S16). If the number has not increased, control, is passed to step S18. If the number has increased, a TDM transmission line of a larger capacity is applied so that the number of TDM transmission lines may be equal or less than the original value for the section (step S17). In step S18, it is determined whether or not the process has been completed for all sections in which the number of wavelengths is exceeded. If NO, control is returned to step S15, and the process is continued. If YES, the process is terminated.
In the case illustrated in FIG. 5, since the number of TDM transmission lines increases for the links between A and B and between D and E, for example, the TDM transmission line of the capacity of 16 is used. If one TDM transmission line of the capacity of 16 is used in addition to three TDM transmission lines of the capacity of 8, all demands may be accommodated, and the total number of TDM transmission lines is four which is the original number of lines.
In the prior art, the TDM transmission line of the capacity of 16 is used at two points between A and B and between D and E. However, as another solution, one TDM transmission line of the capacity of 16 is used as the TDM transmission line between A and E. In this case, the total number of TDM transmission lines between A and E is three. Although the number of TDM transmission lines between A and B and between D and E increases to five, the number of TDM transmission lines between A and E is three. Therefore, the total number of TDM transmission lines between A and B and between D and E is eight. Accordingly, the total number does not exceed the number of wavelengths available for the WDM, and the number of TDM transmission line of the capacity of 16 is one. Thus, in the prior art, the optimum solution that a result of less expensive design is obtained without a TDM transmission line of a larger capacity is not attained. Therefore, the technique of obtaining the optimum solution has been requested in the case above.
The prior art may reduce the resources by a specified rate from the result of facility design and obtain as a solution an optical network facility having the largest reduction amount while satisfying the allowable value of the bypass amount of an optical path or the number of unallowable paths.